# -*- coding: utf-8 -*-
# @Time : 2024/5/28 16:11
# @Author : ZH
# @File : 509.py
# @Software: PyCharm
# class Solution:
#     def fib(self, n: int) -> int:
#
#         d = {0: 0, 1: 1}
#
#         def sum_(a, b):
#             if not (d.get(a) is not None):
#                 d[a] = sum_(a - 1, a - 2)
#             if not (d.get(b) is not None):
#                 d[b] = sum_(b - 1, b - 2)
#             return d[a] + d[b]
#
#
#         return sum_(n - 1, n - 2)


class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        dp = [0] * (n + 1)
        dp[0], dp[1] = 0, 1
        for i in range(2,n+1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]


if __name__ == '__main__':
    so = Solution()
    l = so.fib(3)
    print(l)
